The present invention relates to the field of hierarchical graph partitioning. More specifically, the present invention provides a hierarchical circuit partitioning method for programmable logic devices (PLDs).
As integrated circuits (ICs) become faster, smaller and less expensive, integrated circuits increasingly impact almost every aspect of our daily lives. Although advances in semiconductor fabrication have drastically reduced the cost for producing conventional integrated circuits, the design process is still very expensive and time consuming.
Programmable logic devices (PLDs) offer an alternative to conventional ICs. PLDs are a type of integrated circuit having programmable logic elements and a programmable interconnect. Because PLDs may be programmed to emulate desired digital circuits, the development time needed to go from design to chip implementation may be reduced.
One particular class of PLDs is CPLDs. Each CPLD generally includes two components, logic elements and interconnections. The logic elements may be programmed or configured to perform specific logic functions, for example, NAND, NOR, exclusive OR, etc. The interconnections are routing resources that may be programmed to interconnect the logic elements with each other and with external input/output pins.
Although PLDs have distinct advantages over conventional ICs, configuring the devices is often difficult and computationally expensive. For example, the logic functions must be partitioned (i.e., mapped) among the various logic elements. Poor partitioning wastes interconnection resources and limits the number of functions that may be placed on a PLD.
Similar partitioning problems are found in many other areas. For example, in parallel processing applications, processing tasks must be efficiently partitioned among specific processors. Other partitioning problems will be readily apparent to those of skill in many various arts. In general, the problem is mapping a number of interconnected elements (i.e., logic functions) to a set of resources (i.e., logic elements.)
It is known to arrange these types of partitioning problems as hierarchical graphs. This allows mathematical and computer programming techniques to be used in solving the problem. The graph is arranged with interconnected nodes (or containers) representing the resources and elements representing the elements to be partitioned amongst the elements.
Finding an optimal solution to the problem of graph partitioning is computationally difficult. As the number of elements and resources increase, the number of computations expands exponentially. For large numbers of elements and resources, finding the optimal solution is not possible in a practical sense. Consequently, heuristic techniques have been developed to find good solutions in a reasonable amount of time. However, as PLDs become more and more dense, improved techniques are desirable to closer approximate the optimal solution, and to efficiently manage the number of computations.
Accordingly, there is a need for improved techniques for partitioning hierarchical graphs, and in particular, for an efficient technique for partitioning logic function to particular logic elements within a PLD.